public class Solution4 {
    //238. 除自身以外数组的乘积
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n+1]; //前缀积
        int[] right = new int[n+2]; //后缀积
        left[0] = 1;
        right[n+1] = 1;
        for (int i = 0; i < n; i++) {
            left[i+1] = left[i] * nums[i];
            right[n-i] = right[n+1-i] * nums[n-1-i];
        }
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[i] = left[i] * right[i+2];
        }
        return ret;
    }
}
